package 贪心andDp;

import java.util.Arrays;
import java.util.Scanner;

public class _02渡船问题 {
    /*
        一群N人希望只用一艘船过河，最多只能载两个人。
        因此，必须安排某种穿梭安排，以便前后划船，以便所有人都能通过。
        每个人都有不同的划船速度；一对情侣的速度由较慢的一对决定。
        你的工作是制定一个策略，尽可能缩短这些人的沟通时间。
        输入
        输入的第一行包含一个整数T（1<=T<=20），即测试用例的数量。
        然后是T型病例。
        每个案例的第一行包含N个整数，第二行包含N个整数，表示每个人过河的时间。
        每个案例前面都有一个空行。人数不会超过1000人，没有人需要超过100秒才能过河。
        输出
        对于每个测试用例，打印一行，其中包含所有N人过河所需的总秒数。
        样本输入
        1.
        4.
        1 2 5 10
        样本输出
        17
     */
    //1 2 3 人情况下三个人的通过时间都要加上
    //4人以上的情况下，最短时间是在 a+2b+d和2a+b+c+d之间取最小值  （速度的数组排好序的前提下）
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            int[] speed = new int[n];
            for (int j = 0; j < n; j++) {
                speed[j] = sc.nextInt();
            }
            Arrays.sort(speed);
            f(n, speed);
        }
    }

    private static void f(int n, int[] speed) {
        int left = n;
        int ans = 0;
        while (left > 0) {
            if (left == 1) {//只有1人
                ans += speed[0];
                break;
            } else if (left == 2) {//只有两人
                ans += speed[1];
                break;
            } else if (left == 3) {//有三人
                ans += speed[2] + speed[0] + speed[1];
                break;
            } else {
                //1，2出发，1返回，最后两名出发，2返回
                int s1 = speed[1] + speed[0] + speed[left - 1] + speed[1];
                //1，3出发，1返回，1，4出发，1返回，1，2过河
                int s2 = speed[left - 1] + speed[left - 2] + 2 * speed[0];
                ans += Math.min(s1, s2);
                left -= 2;//左侧是渡河的起点，left代表左侧的剩余人数
            }
        }
        System.out.println(ans);
    }
}
